package sliding_window

/*
930.给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 【非空】子数组。
子数组 是数组的一段连续部分。

示例 1：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2：
输入：nums = [0,0,0,0,0], goal = 0
输出：15
*/

//滑动窗口
//问题转换为和【恰好】为goal的问题
//假设原数组的【前缀和数组】为sum,且子数组(i,j]的区间和为goal,那么sum[j]-sum[i]=goal,因此我们可以枚举j,每次查询满足该等式的i的数量
//对于每一个j,满足sum[j]-sum[i]=goal的i总是落在一个连续的区间中，【i值取区间中的每一个数都满足条件】。并且随着j右移，其对应的区间的左右端点也将右移。
//具体地，我们令滑动窗口右边界为 right，使用两个左边界left1 和 left2 表示左区间 [left1,left2)，此时有left2−left1个区间满足条件。
//在实际代码中，我们需要注意left1 ≤left2 ≤right+1，因此需要在代码中限制 left1 和 left2 不超出范围。
//时间复杂度：O(n)，其中 n 为给定数组的长度。我们至多只需要遍历一次该数组。
//空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
func numSubArraysWithSum(nums []int, goal int) int {
	l1, l2, s1, s2, ans := 0, 0, 0, 0, 0

	// expand window
	for r, num := range nums {
		s1 += num
		// shrink window
		for l1 <= r && s1 > goal {
			s1 -= nums[l1]
			l1++
		}
		s2 += num
		// shrink window
		for l2 <= r && s2 >= goal {
			s2 -= nums[l2]
			l2++
		}
		ans += l2 - l1 // l2-l1个区间满足条件
	}
	return ans
}

//滑动窗口 【恰好】 问题的解决
func numSubArraysWithSumSW(nums []int, goal int) int {
	return atMost(nums, goal) - atMost(nums, goal-1)
}

func atMost(nums []int, goal int) int {
	if goal < 0 {
		return 0
	}
	res, left, right := 0, 0, 0
	for right < len(nums) {
		goal -= nums[right]
		for goal < 0 {
			goal += nums[left]
			left++
		}
		res += right - left + 1
		right++
	}
	return res
}

//哈希表
//假设原数组的前缀和数组为sum,且子数组(i,j]的区间和为goal，那么sum[j]-sum[i]=goal。因此我们可以枚举j,每次查询满足该等式的i的数量。
//用哈希表记录每一种前缀和出现的次数，假设我们当前枚举到元素nums[j],我们只需要查询哈希表中元素sum[j]-goal的数量即可。
//这些元素的数量即对应了以当前j值为右边界的满足条件的子数组的数量。
//最后这些元素的总数量即为所有和为goal 的子数组数量。
//注意：在更新哈希表的时候，以防止i>=j的情况
func numSubArraysWithSumMap(nums []int, goal int) int {
	ans, sum, cnt := 0, 0, map[int]int{}
	for _, num := range nums {
		cnt[sum]++
		sum += num           //前缀和
		ans += cnt[sum-goal] //和 为goal的子数组的数量
	}
	return ans
}

//前缀和,利用切片
//此方案也可以处理负数的情况
func numSubArraysWithSumArray(nums []int, goal int) int {
	ans, psum := 0, 0
	count := make([]int, len(nums)+1)
	count[0] = 1
	for _, i := range nums {
		psum += i
		if psum >= goal {
			ans += count[psum-goal]
		}
		count[psum]++
	}
	return ans
}
